<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /* 
      n个节点构成二叉搜索树的个数
      ①设dp[i]表示i个节点可构成的二叉搜索树
      如果左子树用了j个节点，那么右子树(i-j-1)因此 二叉搜索树的个数为dp[j]*dp[i-j-1]

      因此我们需要定义一个额外变量j，用来循环左子树的个数j<i即可，因为左子树或右子树有一个可以为0，只需要去除一个
      根节点即可

      ②状态转移方程
      i个节点
      dp[i]=dp[j]*dp[i-j-1]
      j从0到i-1
    
      dp[i]=dp[0]*dp[i-0-1]+dp[1]*dp[i-1-1]...+dp[i-1]*dp[0]

      ③初始化dp数组
      dp[0]=dp[1]=1

      ④确定遍历顺序，当前状态依赖于前面状态
      dp[3]=dp[0]*dp[2]...
      因此i从左往右遍历

      */
      var numTrees = function (n) {
        let dp = new Array(n + 1).fill(0);
        dp[0] = dp[1] = 1;
        for (let i = 2; i <= n; i++) {
          for (let j = 0; j < i; j++) {
            dp[i] += dp[j] * dp[i - j - 1];
          }
        }
        return dp[n];
      };
    </script>
  </body>
</html>
